#include "graph.h"
#include "../queue/LinkQueue.h"
#include <malloc.h>
#include <stdio.h>

static void recursive_dfs(TMGraph *graph, int v, int visited[], MGraph_Printf *pFunc)
{
    int i = 0;

    pFunc(graph->v[v]);

    visited[v] = 1;

    printf(", ");

    for (i = 0; i < graph->count; i++)
    {
        if ((graph->matrix[v][i] != 0) && !visited[i])
        {
            recursive_dfs(graph, i, visited, pFunc);
        }
    }
}

static void bfs(TMGraph *graph, int v, int visited[], MGraph_Printf *pFunc)
{
    LinkQueue *queue = LinkQueue_Create();

    if (queue != NULL)
    {
        LinkQueue_Append(queue, graph->v + v);

        visited[v] = 1;

        while (LinkQueue_Length(queue) > 0)
        {
            int i = 0;

            v = (MVertex **)LinkQueue_Retrieve(queue) - graph->v;

            pFunc(graph->v[v]);

            printf(", ");

            for (i = 0; i < graph->count; i++)
            {
                if ((graph->matrix[v][i] != 0) && !visited[i])
                {
                    LinkQueue_Append(queue, graph->v + i);

                    visited[i] = 1;
                }
            }
        }
    }

    LinkQueue_Destroy(queue);
}

/**
 * 功 能：
 *      创建并返回有n个顶点的图
 * 参 数：
 *      v：与顶点相关的数据的指针
 *      n：顶点的个数
 * 返回值：
 *      成功：
 *      失败：NULL
 **/
MGraph *MGraph_Create(MVertex **v, int n) // O(n)
{
    TMGraph *ret = NULL;
    int *p = NULL;

    if ((v == NULL) || (n <= 0))
        goto END;

    // 返回的图的结构体空间
    ret = (TMGraph *)malloc(sizeof(TMGraph));

    if (ret == NULL)
        goto END;

    // 图的顶点的赋值
    ret->count = n;
    // 指向与顶点相关的数据指针，指向顶点
    ret->v = (MVertex **)malloc(sizeof(MVertex *) * n);
    // 申请指向关系的二维数组
    ret->matrix = (int **)malloc(sizeof(int *) * n);

    // 申请矩阵的数据空间
    // calloc : 动态内存分配并做初始化
    p = (int *)calloc(n * n, sizeof(int));

    if ((ret->v != NULL) && (ret->matrix != NULL) && (p != NULL))
    {

        for (int i = 0; i < n; i++)
        {
            // 顶点数据指针保存
            ret->v[i] = v[i];
            // 链接指针到数据空间
            ret->matrix[i] = p + i * n;
        }
    }
    else
    {
        free(p);
        free(ret->matrix);
        free(ret->v);
        free(ret);

        ret = NULL;
    }

END:
    return ret;
}

void MGraph_Destroy(MGraph *graph) // O(1)
{
    TMGraph *tGraph = (TMGraph *)graph;

    if (tGraph != NULL)
    {
        free(tGraph->v);
        free(tGraph->matrix[0]);
        free(tGraph->matrix);
        free(tGraph);
    }
}

void MGraph_Clear(MGraph *graph) // O(n*n)
{
    TMGraph *tGraph = (TMGraph *)graph;

    if (tGraph != NULL)
    {
        int i = 0;
        int j = 0;

        for (i = 0; i < tGraph->count; i++)
        {
            for (j = 0; j < tGraph->count; j++)
            {
                tGraph->matrix[i][j] = 0;
            }
        }
    }
}

int MGraph_AddEdge(MGraph *graph, int v1, int v2, int w) // O(1)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int ret = (tGraph != NULL);

    ret = ret && (0 <= v1) && (v1 < tGraph->count);
    ret = ret && (0 <= v2) && (v2 < tGraph->count);
    ret = ret && (0 <= w);

    if (ret)
    {
        tGraph->matrix[v1][v2] = w;
    }

    return ret;
}

int MGraph_RemoveEdge(MGraph *graph, int v1, int v2) // O(1)
{
    int ret = MGraph_GetEdge(graph, v1, v2);

    if (ret != 0)
    {
        ((TMGraph *)graph)->matrix[v1][v2] = 0;
    }

    return ret;
}

int MGraph_GetEdge(MGraph *graph, int v1, int v2) // O(1)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int condition = (tGraph != NULL);
    int ret = 0;

    condition = condition && (0 <= v1) && (v1 < tGraph->count);
    condition = condition && (0 <= v2) && (v2 < tGraph->count);

    if (condition)
    {
        ret = tGraph->matrix[v1][v2];
    }

    return ret;
}

int MGraph_TD(MGraph *graph, int v) // O(n)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int condition = (tGraph != NULL);
    int ret = 0;

    condition = condition && (0 <= v) && (v < tGraph->count);

    if (condition)
    {
        int i = 0;

        for (i = 0; i < tGraph->count; i++)
        {
            if (tGraph->matrix[v][i] != 0)
            {
                ret++;
            }

            if (tGraph->matrix[i][v] != 0)
            {
                ret++;
            }
        }
    }

    return ret;
}

int MGraph_VertexCount(MGraph *graph) // O(1)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int ret = 0;

    if (tGraph != NULL)
    {
        ret = tGraph->count;
    }

    return ret;
}

int MGraph_EdgeCount(MGraph *graph) // O(n*n)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int ret = 0;

    if (tGraph != NULL)
    {
        int i = 0;
        int j = 0;

        for (i = 0; i < tGraph->count; i++)
        {
            for (j = 0; j < tGraph->count; j++)
            {
                if (tGraph->matrix[i][j] != 0)
                {
                    ret++;
                }
            }
        }
    }

    return ret;
}

void MGraph_DFS(MGraph *graph, int v, MGraph_Printf *pFunc)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int *visited = NULL;
    int condition = (tGraph != NULL);

    condition = condition && (0 <= v) && (v < tGraph->count);
    condition = condition && (pFunc != NULL);
    condition = condition && ((visited = (int *)calloc(tGraph->count, sizeof(int))) != NULL);

    if (condition)
    {
        int i = 0;

        recursive_dfs(tGraph, v, visited, pFunc);

        for (i = 0; i < tGraph->count; i++)
        {
            if (!visited[i])
            {
                recursive_dfs(tGraph, i, visited, pFunc);
            }
        }

        printf("\n");
    }

    free(visited);
}

void MGraph_BFS(MGraph *graph, int v, MGraph_Printf *pFunc)
{
    TMGraph *tGraph = (TMGraph *)graph;
    int *visited = NULL;
    int condition = (tGraph != NULL);

    condition = condition && (0 <= v) && (v < tGraph->count);
    condition = condition && (pFunc != NULL);
    condition = condition && ((visited = (int *)calloc(tGraph->count, sizeof(int))) != NULL);

    if (condition)
    {
        int i = 0;

        bfs(tGraph, v, visited, pFunc);

        for (i = 0; i < tGraph->count; i++)
        {
            if (!visited[i])
            {
                bfs(tGraph, i, visited, pFunc);
            }
        }

        printf("\n");
    }

    free(visited);
}
void MGraph_Display_matrix(MGraph *graph)
{
    if (graph == NULL)
        return;

    TMGraph *tGraph = (TMGraph *)graph;

    printf("\t");
    for (int i = 0; i < tGraph->count; i++)
        printf("|  %s  ", (char *)tGraph->v[i]);
    printf("|\n\n");

    for (int i = 0; i < tGraph->count; i++)
    {
        printf("  |  %s  |", (char *)tGraph->v[i]);
        for (int j = 0; j < tGraph->count; j++)
        {
            if (i == j)
                printf("\e[1;31m");
            else if (tGraph->matrix[i][j] != 0)
                printf("\e[1;32m");
            else
                printf("\e[1;37m");

            printf("  %d", tGraph->matrix[i][j]);
            printf("\e[0m  |");
        }
        printf("\n");
    }
}
void MGraph_Display(MGraph *graph, MGraph_Printf *pFunc) // O(n*n)
{
    TMGraph *tGraph = (TMGraph *)graph;

    if ((tGraph != NULL) && (pFunc != NULL))
    {
        int i = 0;
        int j = 0;

        for (i = 0; i < tGraph->count; i++)
        {
            printf("%d:", i);
            pFunc(tGraph->v[i]);
            printf(" ");
        }

        printf("\n");

        for (i = 0; i < tGraph->count; i++)
        {
            for (j = 0; j < tGraph->count; j++)
            {
                if (tGraph->matrix[i][j] != 0)
                {
                    printf("<");
                    pFunc(tGraph->v[i]);
                    printf(", ");
                    pFunc(tGraph->v[j]);
                    printf(", %d", tGraph->matrix[i][j]);
                    printf(">");
                    printf(" ");
                }
            }
        }

        printf("\n");
    }
}
